package com.lxq.LeetCode.getPermutation;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    public static List<Integer> numSequence = new LinkedList<Integer>() {
        {
            add(1);
            add(2);
            add(3);
            add(4);
            add(5);
            add(6);
            add(7);
            add(8);
            add(9);
        }
    };
    public static String res = "";

    public static void main(String[] args) {
        System.out.println(getPermutation(4, 9));
    }
    //法二：康托展开
    public static String getPermutation2(int n, int k) {
        int[] digit = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        List<Integer> digitList = Arrays.stream(digit).boxed().collect(Collectors.toList());
        int[] factor = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        StringBuilder sb = new StringBuilder();
        k--;
        while (n > 0) {
            int val = k / factor[n - 1];
            sb.append(digitList.get(val + 1));
            digitList.remove(val + 1);
            k = k % factor[n - 1];
            n--;
        }
        return sb.toString();
    }

    public static String getPermutation(int n, int k) {
        if (k == 1) {
            for (int i = 1; i <= n; i++) {
                res += i;
            }
            return res;
        }
        int[] fArrays = factorialArrays(n);
        recursion(n, k, fArrays);
        return res;
    }

    public static void recursion(int n, int k, int[] fArrays) {
        int digits = k / fArrays[n - 1];
        int remainder = k % fArrays[n - 1];
        if (n > 1) {
            res += numSequence.remove(remainder == 0 ? digits - 1 : digits);
            recursion(n - 1, remainder == 0 ? fArrays[n - 1] : remainder, fArrays);
        } else {
            res += numSequence.get(0);
        }

//        if (remainder > 0) {
//            res += numSequence.remove(digits);
//            recursion(n - 1, remainder, fArrays);
//        } else {
//            res += numSequence.remove(digits - 1);
//            res += numSequence.get(0);
//        }
    }

    public static int[] factorialArrays(int n) {
        int[] arr = new int[n + 1];
        arr[0] = 1;
        int last = 0;
        while (last < n) {
            arr[last + 1] = arr[last] * (last + 1);
            last++;
        }
        return arr;
    }
}
